/*
 * Na šachovnici P (obdelnikovou sit m * k) je pevně rozmístěno f bodů.
 * Úkolem je rozmístit dalších b-f bodů, tak aby byl maximální součet matice
 * Euklidovských vzdáleností všech dvojic bodů = sum_i_j d(i,j). Body se nesmějí
 * překrývat.
 *
 * Geometrická interpretace: rozmístit na ploše b bodů tak, aby byly co nejdál
 * od sebe.
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "main.h"
#include "point.h"

#define INPUT_FILE_PATH "./input.txt"


/* unsigned long long int je zoufale málo pro tyto potřeby */

/* unsigned long long int combinations;
 unsigned long long int progress = 0;
 int percents = 0; */

void doWork(void);
void countPossibilities(void);
Point getDiff(int index);
void printPossibilities(int index);
int hasFixedPoint(Point point);
/*
 * Hlavní funkce programu.
 */
int main() {
	FILE *inputFile;
	int i, j;
	int x = 0, y = 0;
	clock_t start, end;
	/* nulové buffery pro výstup --> pro ladění při segfaultech */
	setvbuf(stdout, NULL, _IONBF, 0);
	setvbuf(stderr, NULL, _IONBF, 0);
	freopen("output.txt","w",stdout);

	printf("Vítejte v programu nenávist!\n");

	/* otevřeme soubor se vstupními daty */
	inputFile = fopen(INPUT_FILE_PATH, "r");
	if(inputFile == NULL){
		fprintf(stderr, "ERROR READING INPUT FILE %s\n", INPUT_FILE_PATH);
		return EXIT_FAILURE;
	}

	/* načteme vstupní data */
	loadInput(inputFile);

	/* validace vstupních dat */
	if(b > m * k){
		fprintf(stderr, "Je specifikováno více bodů, než se na plán může vejít (%d > %d*%d)\n", b, m, k);
		return EXIT_FAILURE;
	}
	if(b < f){
		fprintf(
				stderr,
				"Počet pevně umístěných bodů je větší než celkový počet bodů: (b < f, %d < %d). Nelze umístit záporný počet bodů.\n",
				b, f);
		return EXIT_FAILURE;
	}
	for(i = 0; i < f; i++){
		if(fixedPoints[i].x >= m || fixedPoints[i].y >= k){
			fprintf(stderr, "Jedna souřadnice je specifikována mimo plán ([%d, %d])\n", fixedPoints[i].x,
					fixedPoints[i].y);
			return EXIT_FAILURE;
		}
	}

	/* int N = m*k - f, K = b - f;
	 combinations = fact(N)/(fact(K)*fact(N - K)); */

	/* výpis vstupních dat */
	printf("Vstupní data: m = %d, k = %d, f = %d, b = %d.\n", m, k, f, b);
	for(i = 0; i < f; i++){
		printf("%d: [%d,%d] ", i, fixedPoints[i].x, fixedPoints[i].y);
	}
	printf("\n");
	/* printf("Počet kombinací: %d", combinations); */

	/*
	 * Alokace paměti
	 */
	variablePoints = (Point *)malloc((b - f) * sizeof(Point));
	possibilities = (Possibility **)malloc((b - f) * sizeof(Possibility *));
	for(i = 0; i < (b - f); i++){
		possibilities[i] = (Possibility *)malloc(9 * sizeof(Possibility));
	}

	for(i = 0; i < (b - f); i++){
		variablePoints[i].x = x;
		variablePoints[i].y = y;
		if(y < (m - 1)){
			y++;
		}
		else{
			x++;
			y = 0;
		}
		if(hasFixedPoint(variablePoints[i])){
			i--;
		}
	}

	start = clock();
	/* Spuštění práce */
	doWork();

	end = clock();
	printPlane();

	printf("Celkový čas: %f s", ((float) (end - start)) / CLOCKS_PER_SEC);

	return 0;
}

/*
 * Pracovní metoda programu s hlavním cyklem, který má na zodpovědnost zpracovat
 * všechny stavy. Po skončení vypíše nejlepší řešení.
 */
void doWork(void) {
	int i, j;
	int maxIndex;
	int hasPoint;
	int moved;
	/* Počítáme, dokud se některý bod pohnul */
	do{
		moved = 0;
		/* Spočítáme možnosti */
		countPossibilities();
		for(i = 0; i < (b - f); i++){
			/* Seřadíme možnosti podle velikosti */
			bubbleSort(possibilities[i], 9);
			//printPossibilities(i);
			/* A hledáme index takové možnosti, která není blokována jiným bodem.
			 * Hledáme odshora, tj. od možnosti s největším potencionálem.
			 */
			maxIndex = 0;
			do{
				hasPoint = 0;
				/* Blokováno fixním bodem */
				if(hasFixedPoint(possibilities[i][maxIndex].point)){
					hasPoint = 1;
					maxIndex++;
					break;
				}
				/* Blokováno variabilním bodem */
				for(j = 0; j < (b - f); j++){
					if(j != i){
						if(pointEqual(variablePoints[j], possibilities[i][maxIndex].point)){
							hasPoint = 1;
							maxIndex++;
							break;
						}
					}
				}
			}while(hasPoint);
			/* Pokud se jedná o přemístění bodu, poznamenáme si přesun */
			if(!(pointEqual(variablePoints[i], possibilities[i][maxIndex].point))){
				moved = 1;
			}
			/* A bod přesuneme */
			variablePoints[i] = possibilities[i][maxIndex].point;
		}
		//printPlane();
	}while(moved);
}

/**
 * Pro všechny stavy spočítá možnosti jejich přesunu.
 */
void countPossibilities(void){
	int i, j, l;
	double res;
	Point current, possibility;
	/* Pro každý variabilní bod... */
	for(i = 0; i < (b - f); i++){
		current = variablePoints[i];
		/* ... počítáme hodnotu okolních buněk + aktálních souřadnic (nehnutí se). */
		for(j = 0; j < 9; j++){
			res = 0;
			possibility.x = current.x + getDiff(j).x;
			possibility.y = current.y + getDiff(j).y;
			/* Ochrana vytečení z plánu */
			if(possibility.x < 0 || possibility.x >= m || possibility.y < 0 || possibility.y >= k){
				res = -1;
			}
			/* Ochrana proti posunu na fixní bod */
			if(hasFixedPoint(possibility)){
				res = -1;
			}
			/* Pozn.: ochrana proti posunu na variabilní bod není, protože
			 * variabilní body se mohou hýbat.
			 */
			if(res != -1){
				/* Počítání vzdáleností k pevným bodům */
				for(l = 0; l < f; l++){
					res += countDistance(fixedPoints[l], possibility);
				}
				/* Počítání vzdáleností k ostatním variabilním bodům */
				for(l = 0; l < (b - f) - 1; l++){
					if(l != i){
						res += countDistance(variablePoints[l], possibility);
					}
				}
			}
			possibilities[i][j].point = possibility;
			possibilities[i][j].value = res;
		}
	}
}

/*
 * Metoda vrátí změnu souřadnic v závislosti na indexu, viz:
 *    |-1| 0| 1|
 *  --+--+--+--+
 *  -1| 0| 1| 2|
 *  --+--+--+--+
 *   0| 3| 4| 5|
 *  --+--+--+--+
 *   1| 6| 7| 8|
 *  --+--+--+--+
 *  Tj. např. pro "5" vrátí [0, 1].
 *  Používá se pro počítání souřadnic okolí bodu.
 */
Point getDiff(int index){
	Point p;
	switch(index){
	case 0: case 1: case 2:
		p.x = - 1;
		break;
	case 3: case 4: case 5:
		p.x = 0;
		break;
	case 6: case 7: case 8:
		p.x = 1;
	}
	switch(index){
	case 0: case 3: case 6:
		p.y = -1;
		break;
	case 1: case 4: case 7:
		p.y = 0;
		break;
	case 2: case 5: case 8:
		p.y = 1;
	}
	return p;
}

/*
 * Vypíše seznam možností.
 */
void printPossibilities(int index){
	int i;
	printf("Possibilities for point %d: [", index);
	for(i = 0; i < 9; i++){
		printf("[%d, %d]: %f", possibilities[index][i].point.x, possibilities[index][i].point.y, possibilities[index][i].value);
		if(i < 8){
			printf(", ");
		}
	}
	printf("]\n");
}

/*
 * Vrátí TRUE, pokud je na zadaném bodu pevně umístěný bod.
 */
int hasFixedPoint(Point point){
	int i, res = 0;
	for(i = 0; i < f; i++){
		if(pointEqual(point, fixedPoints[i])){
			res = 1;
			break;
		}
	}
	return res;
}
